package leetcode;

import java.util.*;

public class LeetCodeMain94 {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int count=0;
        Map<String,Integer> map=new HashMap<>();
        for (List<String> list:equations){
            for (String s:list){
                if(!map.containsKey(s)){
                    map.put(s,count++);
                }
            }
        }
        double[][] graph=new double[count+1][count+1];
        for (String s:map.keySet()) {
            int x=map.get(s);
            graph[x][x]=1.0;
        }
        int index=0;
        for (List<String> list:equations) {
            String a=list.get(0);
            String b=list.get(1);
            int aa=map.get(a);
            int bb=map.get(b);
            double value=values[index++];
            graph[aa][bb]=value;
            graph[bb][aa]=1/value;
        }
        //通过Floyd算法进行运算
        int n=count+1;
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                for (int k=0;k<n;k++){
                    if(j==k||graph[j][k]!=0) continue;
                    if(graph[j][i]!=0&&graph[i][k]!=0){
                        graph[j][k]=graph[j][i]*graph[i][k];
                    }
                }
            }
        }
        double[] res=new double[queries.size()];
        for (int i = 0; i < res.length; i++) {
            List<String> q=queries.get(i);
            String a=q.get(0);
            String b=q.get(1);
            if (map.containsKey(a)&&map.containsKey(b)){
                double ans=graph[map.get(a)][map.get(b)];
                res[i]=(ans==0?-1:ans);
            }else {
                res[i]=-1;
            }
        }
        return res;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int x=matrix.length-1;
        int y=0;
        while (x>=0&&y<matrix[0].length){
            if (matrix[x][y]<target){
                y++;
            }else if (matrix[x][y]>target){
                x--;
            }else {
                return true;
            }
        }
        return false;
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegress=new int[numCourses];
        List<List<Integer>> adjacency=new ArrayList<>();
        Queue<Integer> queue=new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        for (int[] cp:prerequisites) {
            indegress[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (indegress[i]==0){
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()){
            int pre=queue.poll();
            numCourses--;
            for (int cur:adjacency.get(pre)) {
                if (--indegress[cur]==0){
                    queue.add(cur);
                }
            }
        }
        return numCourses==0;
    }

    public int count;
    public Map<Integer,Integer> map=new LinkedHashMap<>();
    public LeetCodeMain94(int capacity) {
        this.count=capacity;
        map=new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
        if (map.containsKey(key)){
            int value=map.get(key);
            map.remove(key);
            map.put(key,value);
            return value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)){
            map.remove(key);
        }else if (map.size()==count){
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            iterator.next();
            iterator.remove();
        }
        map.put(key,value);
    }

}
